interface ListNode {
	val: number;
	next: ListNode | null;
}

interface TreeNode {
	val: number;
	left: TreeNode | null;
	right: TreeNode | null;
}

interface Candidate {
	node: TreeNode;
	index: number;
}

/**
 * **[1367. 二叉树中的链表](https://leetcode.cn/problems/linked-list-in-binary-tree/)**
 *
 * 给你一棵以 `root` 为根的二叉树和一个 `head` 为第一个节点的链表。
 *
 * 如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 `head` 为首的链表中每个节点的值，那么请你返回 `True` ，否则返回 `False` 。
 *
 * 一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。
 *
 * @param head
 * @param root
 * @returns
 */
export default function isSubPath(head: ListNode | null, root: TreeNode | null): boolean {
	if (head == null || root == null) return head == null;
	return dfs(head, root) || isSubPath(head, root.left) || isSubPath(head, root.right);
}

function dfs(head: ListNode | null, root: TreeNode | null): boolean {
	if (head == null || root == null) return head == null;
	if (head.val != root.val) return false;

	return dfs(head.next, root.left) || dfs(head.next, root.right);
}
